package cn.zhl.tree.redblack;

import cn.zhl.tree.brst.BinaryRotateSearchTree;

import java.util.Comparator;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-05-13 17:21
 **/
public class RBTree<E> extends BinaryRotateSearchTree<E> {
	private static final boolean RED = false;
	private static final boolean BLACK = true;
	public RBTree() {
	}

	public RBTree(Comparator<E> comparator) {
		super(comparator);
	}

	@Override
	protected void afterRemove(Node rnode, Node replacement) {
		RBNode node = (RBNode) rnode;
		if(isRed(node)){
			return;
		}



	}

	@Override
	protected void afterAdd(Node node) {
		//添加的几种情况，首先新添加的必然是红色，后面再考虑不同情况
		RBNode rNode = (RBNode) node;
		RBNode parent = (RBNode)rNode.parent;
		if(parent == null){
			//说明是第一个节点。颜色变为黑色即可。
			black(rNode);
			root = rNode;
			return;
		}
		//如果父节点是黑色，那么直接返回即可
		if(isBlack(parent)){
			return;
		}
		//看uncle节点，是否红色
		RBNode uncle = (RBNode)rNode.uncle();
		RBNode grand = red(parent.parent);
		if(isRed(uncle)){
			black(uncle);
			black(parent);
			afterAdd(grand);
			return;
		}
		if(parent.isLeftChild()){
			if(rNode.isLeftChild()){
				//LL
				black(parent);
			}else{
				//LR
				black(rNode);
				rotateLeft(parent);
			}
			rotateRight(grand);
		}else{
			if(rNode.isLeftChild()){
				//RL
				black(rNode);
				rotateRight(parent);
			}else{
				//RR
				black(parent);
			}
			rotateLeft(grand);
		}
	}

	@Override
	protected Node createNode(E e, Node parent) {
		return new RBNode(e, parent);
	}

	private RBNode color(Node node,boolean color){
		if(node == null){
			return null;
		}
		RBNode rs = (RBNode) node;
		rs.color = color;
		return rs;
	}
	private RBNode red(Node node){
		return color(node,RED);
	}
	private RBNode black(Node node){
		return color(node,BLACK);
	}

	private boolean colorOf(RBNode node){
		return node == null ? BLACK : node.color;
	}
	private boolean isBlack(RBNode node){
		return colorOf(node) == BLACK;
	}
	private boolean isRed(RBNode node){
		return colorOf(node) == RED;
	}


	private class RBNode extends Node{
		boolean color;
		public RBNode(E element, Node parent) {
			super(element, parent);
		}

	}
}
